package sort;

import java.util.Arrays;

public class InsertionSort {


    public static void main(String[] args) {
        int[] arr = {5, 4, 3, 2, 1};

        InsertionSort sort = new InsertionSort();
        System.out.println(Arrays.toString(sort.insertionSort(arr)));

        sort.bubbleSort(arr);

        sort.selectionSort(arr);
    }

    /**
     * 选择排序
     * @param arrs
     */
    public void selectionSort(int[] arrs) {

        int length = arrs.length;

        for (int i = 0; i < length - 1; i++) {
            int minIndex = i;

            for (int j = i + 1; j < length; j++) {
                if(arrs[j] < arrs[minIndex]) {
                    minIndex = j;
                }
            }

            int temp = arrs[minIndex];
            arrs[minIndex] = arrs[i];
            arrs[i] = temp;
        }
        System.out.println(Arrays.toString(arrs));

    }


    /**
     * 冒泡排序
     * @param arrs
     */
    public void bubbleSort(int[] arrs) {

        int length = arrs.length;

        for (int i = 0; i < length - 1; i++) {
            for (int j = 0; j < length - 1 - i; j++) {
                if(arrs[j] > arrs[j + 1]) {
                    int temp = arrs[j + 1];
                    arrs[j + 1] = arrs[j];
                    arrs[j] = temp;
                }
            }
        }
        System.out.println(Arrays.toString(arrs));
    }

    /**
     * 插入排序
     * @param arrs
     * @return
     */
    public int[] insertionSort(int[] arrs) {

        //外循环规定从第二个元素开始，将元素插入到已排好的数组中
        for (int i = 1; i < arrs.length; i++) {

            int preIndex = i - 1;
            int current = arrs[i];

            // 和之前的进行比较判断是否大于上一个 / 是否到达了数组的最前方
            while(preIndex >= 0 && arrs[preIndex] > current) {
                // 如果目标值必前面的大，就把前面的值移动到后面
                arrs[preIndex + 1] = arrs[preIndex];
                // 继续向前移动查找
                preIndex--;
            }
            // 已经排序的数组索引+1
            arrs[preIndex + 1] = current;
        }

        return arrs;
    }
}
